/*
875. 爱吃香蕉的珂珂
https://leetcode.cn/problems/koko-eating-bananas/description/?envType=problem-list-v2&envId=binary-search
难度：中等 李佳韵 2024/09/18
二分查找
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 计算最小的吃香蕉速度，使得在给定时间 h 内吃完所有香蕉堆
    int minEatingSpeed(vector<int>& piles, int h) {
        // 最小速度初始为 1
        int left = 1;
        // 最大速度为香蕉堆中的最大值
        int right = *max_element(piles.begin(), piles.end());
        while (left < right) {
            int mid = left + (right - left) / 2;
            // hours 记录以当前速度 mid 吃完所有香蕉堆所需的时间
            int hours = 0;
            for (int pile : piles) {
                // 向上取整计算吃完当前堆所需时间
                hours += (pile + mid - 1) / mid;
            }
            if (hours > h) {
                // 如果时间超过给定时间 h，说明速度太慢，提高下界
                left = mid + 1;
            } else {
                // 如果时间小于等于给定时间 h，说明速度可能可以更小，缩小上界
                right = mid;
            }
        }
        return left;
    }
};

int main() {
    cout << "请输入香蕉堆的数量：";
    int n;
    cin >> n;
    vector<int> piles;
    cout << "请输入每个香蕉堆的香蕉数量：";
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        piles.push_back(num);
    }
    cout << "请输入吃完所有香蕉堆的时间限制：";
    int h;
    cin >> h;
    Solution solution;
    int result = solution.minEatingSpeed(piles, h);
    cout << "最小的吃香蕉速度为：" << result << endl;
    return 0;
}